from tools.listNode import listToNode, ListNode


class Solution(object):
    p = ListNode()

    def isPalindrome(self, head):
        self.p = head
        return self.recursion(head)

    def recursion(self, head):
        if not head:
            return True
        if not self.recursion(head.next):
            return False
        if self.p.val != head.val:
            return False
        self.p = self.p.next
        return True


print(Solution().isPalindrome(listToNode([1, 2, 3])))
print(Solution().isPalindrome(listToNode([1, 2, 2, 1])))
print(Solution().isPalindrome(listToNode([1, 2, 1])))
